SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Aitken's delta-squared process</title>

</head>

Aitken's delta-squared process

</h1>

</header>

In <a href="Numerical_analysis" title="Numerical analysis">numerical analysis</a>, Aitken's delta-squared process or Aitken extrapolation is a <a href="Series_acceleration" title="Series acceleration">series acceleration</a> method used for accelerating the <a href="Rate_of_convergence" title="Rate of convergence">rate of convergence</a> of a sequence. It is named after <a href="Alexander_Aitken" title="Alexander Aitken">Alexander Aitken</a>, who introduced this method in 1926 as part of an extension to <a href="Bernoulli's_method" title="Bernoulli's method">Bernoulli's method</a>.<a href="#cite_note-1">[1]</a> It is most useful for accelerating the convergence of a sequence that is converging linearly. A precursor form was known to <a href="Seki_K%C5%8Dwa" class="mw-redirect" title="Seki Kōwa">Seki Kōwa</a> (1642 – 1708) and applied to the rectification of the circle, i.e., to the calculation of π.

<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>

Given a sequence <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X={(x_{n})}}">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X={(x_{n})}}</annotation>

</semantics>

</math><img src="./4b3744cefdbfdde791f4600d2dd9c22f27026038.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.436ex; height:2.843ex;" alt="{\displaystyle X={(x_{n})}}" loading="lazy"> with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=0,1,2,3,\ldots ,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=0,1,2,3,\ldots ,}</annotation>

</semantics>

</math><img src="./990634b09ba7646eaec7ed5b5afd3bd68297e79f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:17.036ex; height:2.509ex;" alt="{\displaystyle n=0,1,2,3,\ldots ,}" loading="lazy"> Aitken's delta-squared process associates to this sequence the new sequence

<msub>

</mrow>

</msub>

<mrow>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A[X]=(a_{n})={\left({\frac {x_{n}\,x_{n+2}-x_{n+1}^{2}}{x_{n}+x_{n+2}-2\,x_{n+1}}}\right)},}</annotation>

</semantics>

</math>

which can also be written as

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

<mrow>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A[X]=\left(x_{n}-{\frac {(\Delta x_{n})^{2}}{\Delta ^{2}x_{n}}}\right),}</annotation>

</semantics>

</math>

with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \Delta x_{n}=x_{n+1}-x_{n}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \Delta x_{n}=x_{n+1}-x_{n}}</annotation>

</semantics>

</math><img src="./44fdedee429d5a8453d2e4972966a2be24e6b89b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:17.62ex; height:2.509ex;" alt="{\textstyle \Delta x_{n}=x_{n+1}-x_{n}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \Delta ^{2}x_{n}=x_{n}-2x_{n+1}+x_{n+2}=\Delta x_{n+1}-\Delta x_{n}.}">

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \Delta ^{2}x_{n}=x_{n}-2x_{n+1}+x_{n+2}=\Delta x_{n+1}-\Delta x_{n}.}</annotation>

</semantics>

</math><img src="./a1f40ca672b6bc98dfddc436985db8248982fe90.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:44.98ex; height:2.843ex;" alt="{\textstyle \Delta ^{2}x_{n}=x_{n}-2x_{n+1}+x_{n+2}=\Delta x_{n+1}-\Delta x_{n}.}" loading="lazy"> Both are the same sequence algebraically but the latter has improved <a href="Numerical_stability" title="Numerical stability">numerical stability</a> in computational implementation.

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle A[X]}</annotation>

</semantics>

</math><img src="./eb77d527d2d369c67e6c9208d992e51105f6705f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.017ex; height:2.843ex;" alt="{\textstyle A[X]}" loading="lazy"> is ill-defined if the sequence <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \Delta ^{2}[X]=(\Delta ^{2}x_{n})}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \Delta ^{2}[X]=(\Delta ^{2}x_{n})}</annotation>

</semantics>

</math><img src="./ac9517365a570e879699a6659d2729581411d63d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.71ex; height:3.009ex;" alt="{\textstyle \Delta ^{2}[X]=(\Delta ^{2}x_{n})}" loading="lazy"> contains a zero element, which occurs if the sequence of <a href="Forward_difference" class="mw-redirect" title="Forward difference">forward differences</a>, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \Delta [X]=(\Delta x_{n}),}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \Delta [X]=(\Delta x_{n}),}</annotation>

</semantics>

</math><img src="./d1e62ae6b5ca8ad60ead72b443034393cd76681c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.248ex; height:2.843ex;" alt="{\textstyle \Delta [X]=(\Delta x_{n}),}" loading="lazy"> has any repeated term. From a theoretical point of view, if that occurs only for a finite number of indices, one could apply the Aitken process to only the part of the sequence <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> with indices <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n>n_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n>n_{0}}</annotation>

</semantics>

</math><img src="./deb934b76829498dd1264524bb7a7a1981aed31e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.942ex; height:2.176ex;" alt="{\displaystyle n>n_{0}}" loading="lazy"> such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n_{0}}</annotation>

</semantics>

</math><img src="./63584d203ecb012a7bcb90f422408bbfe4018956.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.449ex; height:2.009ex;" alt="{\displaystyle n_{0}}" loading="lazy"> is the last index for which the sequence <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \Delta [X]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \Delta [X]}</annotation>

</semantics>

</math><img src="./81d8f5234805edcc1318f04d952946c6a93eab23.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.21ex; height:2.843ex;" alt="{\textstyle \Delta [X]}" loading="lazy"> repeats. In practice, the first few terms of the sequence usually provide desired precision; also, when numerically computing the sequence, one has to take care to stop the computation before <a href="Rounding_error" class="mw-redirect" title="Rounding error">rounding errors</a> in the denominator become too large, as the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \Delta ^{2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \Delta ^{2}}</annotation>

</semantics>

</math><img src="./ee3e936424d63793c11b613112cc38af1a98115a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.99ex; height:2.509ex;" alt="{\textstyle \Delta ^{2}}" loading="lazy"> sequence transformation may cancel <a href="Significant_digit" class="mw-redirect" title="Significant digit">significant digits</a>.

<div class="mw-heading mw-heading2"><h2 id="Properties">Properties</h2></div>

Aitken's delta-squared process is an <a href="Acceleration_of_convergence" class="mw-redirect" title="Acceleration of convergence">acceleration of convergence</a> method and a particular case of a nonlinear <a href="Sequence_transformation" title="Sequence transformation">sequence transformation</a>.

A sequence <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle X=(x_{n})}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle X=(x_{n})}</annotation>

</semantics>

</math><img src="./e6bc8c4e993e8cebacd05a319ecdb5d5ab386b38.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.436ex; height:2.843ex;" alt="{\textstyle X=(x_{n})}" loading="lazy"> that converges to a limiting value <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \ell }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \ell }</annotation>

</semantics>

</math><img src="./554d626bee80ffdb3ab924a78a2d05c5a9e642db.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.97ex; height:2.176ex;" alt="{\textstyle \ell }" loading="lazy"> is said to <a href="Rate_of_convergence" title="Rate of convergence">converge linearly</a>, or more technically Q-linearly, if there is some number <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \mu \in (0,1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \mu \in (0,1)}</annotation>

</semantics>

</math><img src="./2f1b7f7b6966819a890ff61371d67495f869f9de.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.41ex; height:2.843ex;" alt="{\textstyle \mu \in (0,1)}" loading="lazy"> for which

</mrow>

</munder>

<mfrac>

<mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lim _{n\to \infty }{\frac {|x_{n+1}-\ell |}{|x_{n}-\ell |}}=\mu .}</annotation>

</semantics>

</math>

This means that asymptotically, the distance between the sequence and its limit shrinks by nearly the same proportion, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu ,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu ,}</annotation>

</semantics>

</math><img src="./1e7e1ef161a49a22b500d63307460ad92eeb6a16.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.049ex; height:2.176ex;" alt="{\displaystyle \mu ,}" loading="lazy"> on every step and the ratio of reduction becomes closer and closer to that proportion. This is also sometimes called "geometric convergence," since it is a characteristic property for <a href="Geometric_series" title="Geometric series">geometric series</a>, or "exponential convergence," since it is convergence like <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu ^{n}=\exp(n\ln \mu ).}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu ^{n}=\exp(n\ln \mu ).}</annotation>

</semantics>

</math><img src="./9519cb1cc94b35a869fb193c860ee1ec3eaefe84.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.237ex; height:2.843ex;" alt="{\displaystyle \mu ^{n}=\exp(n\ln \mu ).}" loading="lazy">

Aitken's method will accelerate the convergence of a sequence <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A[X]=(a_{n}),}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A[X]=(a_{n}),}</annotation>

</semantics>

</math><img src="./8fadf247fe027a8ebf3377e3bd25ffd8c98855a0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.02ex; height:2.843ex;" alt="{\displaystyle A[X]=(a_{n}),}" loading="lazy"> with terms defined above, satisfies <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \lim _{n\to \infty }{\frac {a_{n}-\ell }{x_{n}-\ell }}=0.}">

</mrow>

</munder>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \lim _{n\to \infty }{\frac {a_{n}-\ell }{x_{n}-\ell }}=0.}</annotation>

</semantics>

</math><img src="./5fab64864fbefdf3f507e051f653fe1451814f9d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.505ex; width:17.735ex; height:4.176ex;" alt="{\textstyle \lim _{n\to \infty }{\frac {a_{n}-\ell }{x_{n}-\ell }}=0.}" loading="lazy">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"> is not a linear operator on sequences, but it is linear with respect to addition of constant sequences: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle A[X-C]=A[X]-C,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle A[X-C]=A[X]-C,}</annotation>

</semantics>

</math><img src="./1a21c3d295754db631affbba2f9b404702b3b63a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.992ex; height:2.843ex;" alt="{\textstyle A[X-C]=A[X]-C,}" loading="lazy"> if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"> is any constant sequence <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C=(c)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C=(c)}</annotation>

</semantics>

</math><img src="./8bc38f9dce843eebf473d0fde8b7b439bf2ad0c6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.681ex; height:2.843ex;" alt="{\displaystyle C=(c)}" loading="lazy">, constant for all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n.}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n.}</annotation>

</semantics>

</math><img src="./e59df02a9f67a5da3c220f1244c99a46cc4eb1c6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.042ex; height:1.676ex;" alt="{\displaystyle n.}" loading="lazy"> This is clear from the expression of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A[X]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A[X]}</annotation>

</semantics>

</math><img src="./40abd94a808a2369931fac9811cbd1cbdd44497d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.017ex; height:2.843ex;" alt="{\displaystyle A[X]}" loading="lazy"> in terms of the <a href="Finite_difference" title="Finite difference">finite difference</a> <a href="Operator_(mathematics)" title="Operator (mathematics)">operator</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Delta .}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Delta .}</annotation>

</semantics>

</math><img src="./6f768bd0f5ad6d36e95172cf0e044e88c5d119dc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.583ex; height:2.176ex;" alt="{\displaystyle \Delta .}" loading="lazy">

The new process does not in general converge quadratically, but for an <a href="Iterated_function" title="Iterated function">iterated function</a> sequence satisfying <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{n+1}=f(x_{n})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{n+1}=f(x_{n})}</annotation>

</semantics>

</math><img src="./643700935b0ff5e6dd286c1ec5dbb1605be82171.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.383ex; height:2.843ex;" alt="{\displaystyle x_{n+1}=f(x_{n})}" loading="lazy"> for some function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> converging to a <a href="Fixed_point_(mathematics)" title="Fixed point (mathematics)">fixed point</a>, the accelerated sequence's convergence is quadratic. In this case, the technique is known as <a href="Steffensen's_method" title="Steffensen's method">Steffensen's method</a>.

Empirically, the A-operation eliminates the "most important error term". One can check this by considering a sequence of the form <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{n}=\ell +a^{n}+b^{n}}">

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{n}=\ell +a^{n}+b^{n}}</annotation>

</semantics>

</math><img src="./7d2a005b4f9e3c88ff97d2a756545110956a0a21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:16.961ex; height:2.676ex;" alt="{\displaystyle x_{n}=\ell +a^{n}+b^{n}}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0<b<a<1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0<b<a<1}</annotation>

</semantics>

</math><img src="./f4035a13593478714900fb3d52863494604486a7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:13.848ex; height:2.176ex;" alt="{\displaystyle 0<b<a<1}" loading="lazy">:

The sequence <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A[X]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A[X]}</annotation>

</semantics>

</math><img src="./40abd94a808a2369931fac9811cbd1cbdd44497d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.017ex; height:2.843ex;" alt="{\displaystyle A[X]}" loading="lazy"> will then go to the limit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \ell }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \ell }</annotation>

</semantics>

</math><img src="./554d626bee80ffdb3ab924a78a2d05c5a9e642db.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.97ex; height:2.176ex;" alt="{\textstyle \ell }" loading="lazy"> like <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b^{n}}</annotation>

</semantics>

</math><img src="./b8f8f52cd26bb201e02c8d1b3619a3a682f44dbc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.216ex; height:2.343ex;" alt="{\displaystyle b^{n}}" loading="lazy"> goes to zero.

Geometrically, the graph of an exponential function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(t)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(t)}</annotation>

</semantics>

</math><img src="./5bf044fe2fbfc4bd8d6d7230f4108430263f9fd6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.927ex; height:2.843ex;" alt="{\displaystyle f(t)}" loading="lazy"> that satisfies <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(n)=x_{n}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(n)=x_{n}}</annotation>

</semantics>

</math><img src="./4ea5f752799c2781b3d9122aae7e4053e56c8399.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.129ex; height:2.843ex;" alt="{\displaystyle f(n)=x_{n}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(n+1)=x_{n+1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(n+1)=x_{n+1}}</annotation>

</semantics>

</math><img src="./53029b50bd264c8d8027f7d8f859e9072e864738.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.233ex; height:2.843ex;" alt="{\displaystyle f(n+1)=x_{n+1}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(n+2)=x_{n+2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(n+2)=x_{n+2}}</annotation>

</semantics>

</math><img src="./94def5b026a9d8fb610766a99f8e3f216f97f425.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.233ex; height:2.843ex;" alt="{\displaystyle f(n+2)=x_{n+2}}" loading="lazy"> has a horizontal asymptote at <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {x_{n}x_{n+2}-x_{n+1}^{2}}{x_{n}-2x_{n+1}+x_{n+2}}}}">

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {x_{n}x_{n+2}-x_{n+1}^{2}}{x_{n}-2x_{n+1}+x_{n+2}}}}</annotation>

</semantics>

</math><img src="./fab83f9ff8a4a53fc39f16c7ea8449ea1098a46d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:19.525ex; height:6.509ex;" alt="{\displaystyle {\frac {x_{n}x_{n+2}-x_{n+1}^{2}}{x_{n}-2x_{n+1}+x_{n+2}}}}" loading="lazy"> (if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{n}-2x_{n+1}+x_{n+2}\neq 0}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{n}-2x_{n+1}+x_{n+2}\neq 0}</annotation>

</semantics>

</math><img src="./8a3ce0f56e9ac1f32a482069f13ad0dd9536adc5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.95ex; height:2.676ex;" alt="{\displaystyle x_{n}-2x_{n+1}+x_{n+2}\neq 0}" loading="lazy">).

One can also show that if a sequence <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> converges to its limit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell }</annotation>

</semantics>

</math><img src="./f066e981e530bacc07efc6a10fa82deee985929e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.97ex; height:2.176ex;" alt="{\displaystyle \ell }" loading="lazy"> at a rate strictly greater than 1, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A[X]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A[X]}</annotation>

</semantics>

</math><img src="./40abd94a808a2369931fac9811cbd1cbdd44497d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.017ex; height:2.843ex;" alt="{\displaystyle A[X]}" loading="lazy"> does not have a better rate of convergence. (In practice, one rarely has e.g. quadratic convergence which would mean over 30 (respectively 100) correct decimal places after 5 (respectively 7) iterations (starting with 1 correct digit); usually no acceleration is needed in that case.)

In practice, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A[X]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A[X]}</annotation>

</semantics>

</math><img src="./40abd94a808a2369931fac9811cbd1cbdd44497d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.017ex; height:2.843ex;" alt="{\displaystyle A[X]}" loading="lazy"> often converges much faster to the limit than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> does, as demonstrated by the example calculations below.

Usually, it is much cheaper to calculate <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A[X]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A[X]}</annotation>

</semantics>

</math><img src="./40abd94a808a2369931fac9811cbd1cbdd44497d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.017ex; height:2.843ex;" alt="{\displaystyle A[X]}" loading="lazy"> (involving only calculation of differences, one multiplication and one division) than to calculate many more terms of the sequence <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy">. Care must be taken, however, to avoid introducing errors due to insufficient precision when calculating the differences in the numerator and denominator of the expression.

<div class="mw-heading mw-heading2"><h2 id="Example_calculations">Example calculations</h2></div>

Example 1: The value of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\sqrt {2}}\approx 1.4142136}">

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\sqrt {2}}\approx 1.4142136}</annotation>

</semantics>

</math><img src="./6ca3f0f739cceb7d3f7c458368348c9e758ab5a8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:16.143ex; height:3.009ex;" alt="{\displaystyle {\sqrt {2}}\approx 1.4142136}" loading="lazy"> can be approximated by assuming an initial value for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{0}}</annotation>

</semantics>

</math><img src="./86f21d0e31751534cd6584264ecf864a6aa792cf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.384ex; height:2.009ex;" alt="{\displaystyle x_{0}}" loading="lazy"> and iterating the following sequence, called <a href="Heron's_method" class="mw-redirect" title="Heron's method">Heron's method</a>:

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

<mfrac>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{n+1}={\frac {x_{n}+{\frac {2}{x_{n}}}}{2}}.}</annotation>

</semantics>

</math>

Starting with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{0}=1:}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{0}=1:}</annotation>

</semantics>

</math><img src="./ecbf0b3d4a6f63b3638104a9e619d6310c4ec515.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.937ex; height:2.509ex;" alt="{\displaystyle x_{0}=1:}" loading="lazy">

<th>n

</th>

<th>X

</th>

<th>A[X]

</th></tr>

<tr>

<td>0

</td>

<td>1

</td>

<td>1.4285714

</td></tr>

<tr>

<td>1

</td>

<td>1.5

</td>

<td>1.4141414

</td></tr>

<tr>

<td>2

</td>

<td>1.4166667

</td>

<td>1.4142136

</td></tr>

<tr>

<td>3

</td>

<td>1.4142157

</td>

<td>--

</td></tr>

<tr>

<td>4

</td>

<td>1.4142136

</td>

<td>--

</td></tr></tbody></table>

It is worth noting here that Aitken's method does not save the cost of calculating two iterations here; computation of the first three <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle A[X]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle A[X]}</annotation>

</semantics>

</math><img src="./eb77d527d2d369c67e6c9208d992e51105f6705f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.017ex; height:2.843ex;" alt="{\textstyle A[X]}" loading="lazy"> values required the first five <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle X}</annotation>

</semantics>

</math><img src="./8d80c41192705e1a6c6de1d65e16d7f70fbac391.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\textstyle X}" loading="lazy"> values. Also, the second <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle A[X]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle A[X]}</annotation>

</semantics>

</math><img src="./eb77d527d2d369c67e6c9208d992e51105f6705f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.017ex; height:2.843ex;" alt="{\textstyle A[X]}" loading="lazy"> value is less accurate than the 4th <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle X}</annotation>

</semantics>

</math><img src="./8d80c41192705e1a6c6de1d65e16d7f70fbac391.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\textstyle X}" loading="lazy"> value, which is not surprising due to the fact that Aitken's process is best suited for sequences that converge linearly, rather than quadratically, and Heron's method for calculating square roots converges quadratically.

Example 2: The value of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {\pi }{4}}}">

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {\pi }{4}}}</annotation>

</semantics>

</math><img src="./1f89d7c88c1c93dce69a46052a8e276e231063de.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:2.168ex; height:4.676ex;" alt="{\displaystyle {\frac {\pi }{4}}}" loading="lazy"> may be calculated as an infinite sum via the <a href="Leibniz_formula_for_%CF%80" title="Leibniz formula for π">Leibniz formula for π:</a>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

<mfrac>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {\pi }{4}}=\sum _{n=0}^{\infty }{\frac {(-1)^{n}}{2n+1}}\approx 0.785398}</annotation>

</semantics>

</math>

<th>n

</th>

<th>Series Terms

</th>

<th>X = Partial Sums

</th>

<th>A[X]

</th></tr>

<tr>

<td>0

</td>

<td>1

</td>

<td>1

</td>

<td>0.79166667

</td></tr>

<tr>

<td>1

</td>

<td>−0.33333333

</td>

<td>0.66666667

</td>

<td>0.78333333

</td></tr>

<tr>

<td>2

</td>

<td>0.2

</td>

<td>0.86666667

</td>

<td>0.78630952

</td></tr>

<tr>

<td>3

</td>

<td>−0.14285714

</td>

<td>0.72380952

</td>

<td>0.78492063

</td></tr>

<tr>

<td>4

</td>

<td>0.11111111

</td>

<td>0.83492063

</td>

<td>0.78567821

</td></tr>

<tr>

<td>5

</td>

<td>−9.0909091×10−2

</td>

<td>0.74401154

</td>

<td>0.78522034

</td></tr>

<tr>

<td>6

</td>

<td>7.6923077×10−2

</td>

<td>0.82093462

</td>

<td>0.78551795

</td></tr>

<tr>

<td>7

</td>

<td>-6.6666667×10−2

</td>

<td>0.75426795

</td>

<td>--

</td></tr>

<tr>

<td>8

</td>

<td>5.8823529×10−2

</td>

<td>0.81309148

</td>

<td>--

</td></tr></tbody></table>

In this example, Aitken's method is applied to a sublinearly converging series and accelerates convergence considerably. The convergence is still sublinear, but much faster than the original convergence: the first <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle A[X]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle A[X]}</annotation>

</semantics>

</math><img src="./eb77d527d2d369c67e6c9208d992e51105f6705f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.017ex; height:2.843ex;" alt="{\textstyle A[X]}" loading="lazy"> value, whose computation required the first three <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle X}</annotation>

</semantics>

</math><img src="./8d80c41192705e1a6c6de1d65e16d7f70fbac391.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\textstyle X}" loading="lazy"> values, is closer to the limit than the eighth <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle X}</annotation>

</semantics>

</math><img src="./8d80c41192705e1a6c6de1d65e16d7f70fbac391.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\textstyle X}" loading="lazy"> value.

<div class="mw-heading mw-heading2"><h2 id="Example_pseudocode_for_Aitken_extrapolation">Example pseudocode for Aitken extrapolation</h2></div>

The following is an example of using the Aitken extrapolation to help find the limit of the sequence <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{n+1}=f(x_{n})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{n+1}=f(x_{n})}</annotation>

</semantics>

</math><img src="./643700935b0ff5e6dd286c1ec5dbb1605be82171.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.383ex; height:2.843ex;" alt="{\displaystyle x_{n+1}=f(x_{n})}" loading="lazy"> when given some initial <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{0},}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{0},}</annotation>

</semantics>

</math><img src="./c8b35dd572e629881da4083ad1681bc7cf420304.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.031ex; height:2.009ex;" alt="{\displaystyle x_{0},}" loading="lazy"> where the limit of this sequence is assumed to be a fixed point <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> (say <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha =f(\alpha )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha =f(\alpha )}</annotation>

</semantics>

</math><img src="./0f6170d08059f812d1dcdf730a1c0abb0d67d137.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.162ex; height:2.843ex;" alt="{\displaystyle \alpha =f(\alpha )}" loading="lazy">). For instance, if the sequence is given by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle x_{n+1}={\frac {1}{2}}\left(x_{n}+{\frac {2}{x_{n}}}\right)}">

<msub>

</mrow>

</msub>

<mfrac>

</mfrac>

</mrow>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<mfrac>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle x_{n+1}={\frac {1}{2}}\left(x_{n}+{\frac {2}{x_{n}}}\right)}</annotation>

</semantics>

</math><img src="./68fbd2f369ef720b4de74a0c2438bcc08c9cee0b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:20.698ex; height:4.843ex;" alt="{\textstyle x_{n+1}={\frac {1}{2}}\left(x_{n}+{\frac {2}{x_{n}}}\right)}" loading="lazy"> with starting point <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{0}=1,}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{0}=1,}</annotation>

</semantics>

</math><img src="./548eee77e100e5eb64551ee9f07207d65e04049f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.292ex; height:2.509ex;" alt="{\displaystyle x_{0}=1,}" loading="lazy"> then the function will be <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle f(x):={\frac {1}{2}}\left(x+{\frac {2}{x}}\right),}">

<mfrac>

</mfrac>

</mrow>

<mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle f(x):={\frac {1}{2}}\left(x+{\frac {2}{x}}\right),}</annotation>

</semantics>

</math><img src="./baaf722b307cdcf14945e3a02ce13df81d26e6a9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:19.318ex; height:3.509ex;" alt="{\textstyle f(x):={\frac {1}{2}}\left(x+{\frac {2}{x}}\right),}" loading="lazy"> which has <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha :={\sqrt {2}}}">

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha :={\sqrt {2}}}</annotation>

</semantics>

</math><img src="./6d8c8e4354d64f8d1e7f4716b89a50a912848c5f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.331ex; height:3.009ex;" alt="{\displaystyle \alpha :={\sqrt {2}}}" loading="lazy"> as a fixed point (see <a href="Methods_of_computing_square_roots" class="mw-redirect" title="Methods of computing square roots">Methods of computing square roots</a>); it is this fixed point whose value will be approximated.

This pseudo code also computes the Aitken approximation to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f^{\prime }(\alpha )}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f^{\prime }(\alpha )}</annotation>

</semantics>

</math><img src="./03082452339a40d9e9cd62027df4d88b0bdc5306.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.302ex; height:3.009ex;" alt="{\displaystyle f^{\prime }(\alpha )}" loading="lazy">. The Aitken extrapolates will be denoted by <code>aitkenX</code>. During the computation of the extrapolate, it is important to check if the denominator becomes too small, which could happen if we already have a large amount of accuracy; without this check, a large amount of error could be introduced by the division. This small number will be denoted by <code>epsilon</code>. Because the binary representation of the fixed point could be infinite (or at least too large to fit in the available memory), the calculation will stop once the approximation is within <code>tolerance</code> of the true value.

<div class="mw-highlight mw-highlight-lang-matlab mw-content-ltr" dir="ltr"><pre>%These choices depend on the problem being solved

x0 = 1 %The initial value

f(x) = (1/2)*(x + 2/x) %The function that finds the next element in the sequence

tolerance = 10^-10 %10 digit accuracy is desired

epsilon = 10^-16 %Do not divide by a number smaller than this

maxIterations = 20 %Do not allow the iterations to continue indefinitely

haveWeFoundSolution = false %Were we able to find the solution to within the desired tolerance? not yet

for i = 1 : maxIterations

x1 = f(x0)

x2 = f(x1)

if (x1 ~= x0)

lambda = absoluteValue((x2 - x1)/(x1 - x0)) %OPTIONAL: Computes an approximation of |f'(fixedPoint)|, which is denoted by lambda

end

denominator = (x2 - x1) - (x1 - x0);

if (absoluteValue(denominator) < epsilon) %To avoid greatly increasing error, do not divide by too small of a number

print('WARNING: denominator is too small')

break %Leave the loop

end

aitkenX = x2 - ( (x2 - x1)^2 )/denominator

if (absoluteValue(aitkenX - x2) < tolerance) %If the value is within tolerance

print("The fixed point is ", aitkenX)) %Display the result of the Aitken extrapolation

haveWeFoundSolution = true

break %Done, so leave the loop

end

x0 = aitkenX %Update x0 to start again

end

if (haveWeFoundSolution == false) %If we were not able to find a solution to within the desired tolerance

print("Warning: Not able to find solution to within the desired tolerance of ", tolerance)

print("The last computed extrapolate was ", aitkenX)

end

</pre></div>

<ul><li><a href="Rate_of_convergence" title="Rate of convergence">Rate of convergence</a></li>

<li><a href="Limit_of_a_sequence" title="Limit of a sequence">Limit of a sequence</a></li>

<li><a href="Fixed_point_iteration" class="mw-redirect" title="Fixed point iteration">Fixed point iteration</a></li>

<li><a href="Richardson_extrapolation" title="Richardson extrapolation">Richardson extrapolation</a></li>

<li><a href="Sequence_transformation" title="Sequence transformation">Sequence transformation</a></li>

<li><a href="Shanks_transformation" title="Shanks transformation">Shanks transformation</a></li>

<li><a href="Steffensen's_method" title="Steffensen's method">Steffensen's method</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFAitken1926" class="citation journal cs1"><a href="Alexander_Aitken" title="Alexander Aitken">Aitken, Alexander</a> (1926). "On Bernoulli's numerical solution of algebraic equations". Proceedings of the Royal Society of Edinburgh. 46: 289–305. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1017%2FS0370164600022070">10.1017/S0370164600022070</a>.</cite>

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<ul><li>William H. Press, et al., Numerical Recipes in C, (1987) Cambridge University Press, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-521-43108-5</bdi> (See <a rel="nofollow" class="external text" href="http://apps.nrbook.com/c/index.html">section 5.1</a>)</li>

<li>Abramowitz and Stegun, <a href="Abramowitz_and_Stegun" title="Abramowitz and Stegun">Handbook of Mathematical Functions</a>, section 3.9.7</li>

<li>Kendall E. Atkinson, An Introduction to Numerical Analysis, (1989) John Wiley & Sons, Inc, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-471-62489-6</bdi></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-05-19" href="https://en.wikipedia.org/wiki/?title=Aitken's_delta-squared_process&oldid=1291219877">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>